# -*- coding: utf-8 -*-

'''
@author: 5822 - Duarte Marques & 5955 - João Rosa
@date: 06 de Junho de 2013
@obs: Trabalho de Estruturas de Dados e Algoritmos
      Docente: Prof. Jasnau Caeiro
'''
#pseudo-code from: http://en.wikipedia.org/wiki/Comb_sort

class Comb_Sort:
    '''
    Classe que contém o algoritmo Comb Sort.
    '''
    
    def __init__(self, A):
        '''
        Metodo que inicializa a variavel "A", que 
        diz respeito a uma lista.
        '''
        self.A = A
        pass

    def comb_sort(self):
        '''
        Metodo que contén o algoritmo "Comb Sort",
        mais um algoritmo de ordenação.
        '''
        gap = len(self.A)
        shrink = 1.3
        swaps = True
        while gap > 1 or swaps == True:
            gap = int(gap/shrink)
            if gap < 1:
                gap = 1
            i = 0
            swaps = False
            
            while i + gap < len(self.A):
                j = i + gap
                if self.A[i] > self.A[j]:
                    self.A[i], self.A[j] = self.A[j], self.A[i]
                    swaps = True
                    pass
                i = i + 1
        return self.A
            

# A = [9,5,3,6,2,65,7,5,1,8]
# print A
# Cs = Comb_Sort(A)
# print Cs.comb_sort()
